﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <iomanip>

using namespace std;


class Solution {
public:
    string minWindow(string s, string t) {
        int hash1[128] = { 0 };
        int hash2[128] = { 0 };
        int num = 0;
        for (int i = 0; i < t.size(); i++)
        {
            if (hash1[t[i]] == 0) num++;
            hash1[t[i]]++;
        }

        int left = 0, right = 0, tmp = 0;
        int index = 0, len = 999999;
        string ret = "";
        while (right < s.size())
        {
            hash2[s[right]]++;
            if (hash1[s[right]] > 0 && hash2[s[right]] == hash1[s[right]]) tmp++;

            if (tmp == num)
            {
                while (left <= right && tmp == num)
                {   
                    hash2[s[left]]--;
                    if (hash1[s[left]] > 0)
                    {    
                        if (hash2[s[left]] < hash1[s[left]]) tmp--;
                    }
                    left++;
                }
                if (right - (left - 1) + 1 < len)
                {
                    len = right - (left - 1) + 1;
                    index = left - 1;
                }
            }
            right++;
        }

        ret = s.substr(index, len);
        return ret;
    }
};



int main()
{
    string ret = Solution().minWindow("ADOBECODEBANC", "ABC");
    cout << ret;
	return 0;
}